package __贪心算法

/*
https://leetcode.cn/problems/candy/

135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
  - 1.每个孩子至少分配到 1 个糖果。
  - 2/相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

	第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
*/
func candy(ratings []int) int {
	/**先确定一边，再确定另外一边
	    1.先从左到右，当右边的大于左边的就加1
	    2.再从右到左，当左边的大于右边的就再加1
	**/
	need := make([]int, len(ratings)) //声明糖果数组
	sum := 0

	for i := 0; i < len(ratings); i++ { // 初始化(每个人至少一个糖果)
		need[i] = 1
	}

	for i := 0; i < len(ratings)-1; i++ { // 1.先从左到右，当右边的大于左边的就加1
		if ratings[i] < ratings[i+1] {
			need[i+1] = need[i] + 1
		}
	}
	for i := len(ratings) - 1; i > 0; i-- { // 2.再从右到左，当左边的大于右边的就右边加1，但要花费糖果最少，所以需要做下判断
		if ratings[i-1] > ratings[i] {
			need[i-1] = max(need[i-1], need[i]+1)
		}
	}

	for i := 0; i < len(ratings); i++ { //计算总共糖果
		sum += need[i]
	}

	return sum
}
